#include<iostream>
using namespace std;
bool Paymoney(int arr[],int length,int paymoney)//F[i]代表凑齐i元的最少硬币个数 
{
	int** result = new int* [length]();
	for (int i = 0; i < length; i++)//创建二维数组存放需求量和面额数量
	{
		result[i] = new int[paymoney + 1]();
	}
	for (int row = 0; row <= length; row++)//钱币面额
	{
		for (int col = 1; col <= paymoney; col++)//硬币面值的个数 
		{
			if (row == 0)//第一行只有一种面额，需要的钱数是用所需支付的钱除以第一行的面额
				result[row][col] = col / arr[row];
			else if (col < arr[row])//面额大于所需支付的钱，则沿用上行钱数
				result[row][col] = result[row - 1][col];
			else
				if ((col / arr[row] + result[row - 1][col % arr[row]]) < result[row - 1][col])//不能刚好支付，用上一行余下的所需支付金额，二者相加对比上一行面额的钱数，用小的
					result[row][col] = col / arr[row] + result[row - 1][col % arr[row]];
				else
					result[row][col] = result[row - 1][col];
		}
	}
		delete[](result);
		return true;
}
int main()
{
	int arr[10] = { 1,2,5,10,20,50,100 };
	int length = 7;
	int paymoney;
	cout << "请输入需要支付的金额：";
	cin >> paymoney;
	Paymoney(arr, paymoney, length);
	return 0;
}